# -*- coding:utf-8
'''
作者: Jia
日期: 2022年04月22日
描述: https://leetcode-cn.com/problems/sum-of-all-odd-length-subarrays/
'''

from typing import List


class Solution:
    
    def sumOddLengthSubarrays1(self, arr: List[int]) -> int:
        # 普通方法
        sum = 0
        length = len(arr)
        for start in range(length):
            end = start
            while end < length:
                for i in range(start, end+1):
                    sum += arr[i]
                end += 2
        return sum
    
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        # 前缀和
        sum = 0
        n = len(arr)
        prefix_sum = [0] * (n+1)
        for i, v in enumerate(arr):
            prefix_sum[i+1] = prefix_sum[i] + v
        
        for start in range(n):
            end = start
            while end < n:
                sum += prefix_sum[end + 1] - prefix_sum[start]
                end += 2
        return sum

s = Solution()
print(s.sumOddLengthSubarrays([1,4,2,5,3]))